public class code2 {
    // 牛客 top 101 在二叉树中找到两个节点的最近公共祖先


    // 这道题目的递归方式比较难理解，还是注重理解一下 hashMap 形式下的解决方式

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */

    // 使用非递归的形式书写一下代码
    // 递归看不懂。。。
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        // 首先，定义一个顺序表，将当前二叉树中的信息按照中序遍历的形式存储
        ArrayList<Integer> list = new ArrayList<>();
        InputCur(list, root);
        // 这里将通过 HashMap 来记录下每一个节点值对应的下标信息
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < list.size(); i++) {
            map.put(list.get(i), i);
        }
        while (root != null) {
            // 获取到当前根节点的下标值
            int k = map.get(root.val);
            if(map.get(o1) < k && map.get(o2) < k) {
                // 此时就说明两个值都在该根节点的左侧
                root = root.left;
                // 需要注意的是 这里的三个判断条件是需要联系起来的，不能出现单个 if 判断的情况，否则会出现 少判断个别情况的问题！！！
            }else if(map.get(o1) > k && map.get(o2) > k) {
                // 此时说明两个值都在根节点的右侧
                root = root.right;
            }else {
                // 排除上面的两种情况后，此时就说明两个值在该根节点的 两边
                return root.val;
            }
        }
        return 0;
    }

    private static void InputCur(ArrayList<Integer> list, TreeNode root) {
        // 这里采用中序遍历的原因是
        // 中序遍历会将二叉树中的值分割为两部分
        // 这样就可以通过 hashMap 将元素进行标记向两边来获取相关信息
        if(root == null) {
            return;
        }
        InputCur(list, root.left);
        list.add(root.val);
        InputCur(list, root.right);
    }
}
